package com.weilive.core.utils;

import java.util.Comparator;

public class QuickSort {

	/** 
	 * @param <T>
	 * @param pData 需要排序的数组 
	 * @param left  左边的位置,初始值为0 
	 * @param right 右边的位置,初始值为数组长度 
	 */ 
	public static <T> void sort(T[] pData,int left,int right, Comparator<T> comparator) 
	{ 
		int i,j; 
		T first,temp; 
		i = left; 
		j = right; 
		first = pData[left]; //这里选其他的数也行，不过一般选第一个
		//一趟快速排序 
		while(true) 
		{ 
			//从第二个数开始找大于中枢的数 ,从前面开始找大于pData[left]的数
			while((++i)<right-1 && comparator.compare(pData[i], first) < 0); 
			//从最后一个数开始找第一个小于中枢pData[left]的数 
			while((--j)>left && comparator.compare(pData[j], first) > 0); 
			if(i>=j) 
				break; 
			//交换两边找到的数 
			temp = pData[i]; 
			pData[i] = pData[j]; 
			pData[j] = temp; 

		} 
		//交换中枢 
		pData[left] = pData[j]; 
		pData[j] = first; 
		//递归快排中枢左边的数据 
		if(left<j) 
			sort(pData,left,j, comparator); 
		//递归快排中枢右边的数据 
		if(right>i) 
			sort(pData,i,right, comparator); 
	} 
}
